<!DOCTYPE html>



  


<html class="theme-next mist use-motion" lang="zh-CN">
<head><meta name="generator" content="Hexo 3.8.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="Hexo, NexT">










<meta name="description" content="进程调度程序可看做在可运行态进程之间分配有限的处理器时间资源的内核子系统。">
<meta property="og:type" content="article">
<meta property="og:title" content="Linux系统之进程调度">
<meta property="og:url" content="http://luqilinok.github.io/2019/07/17/kernel-3/index.html">
<meta property="og:site_name" content="Lu QiLin&#39;s Blog">
<meta property="og:description" content="进程调度程序可看做在可运行态进程之间分配有限的处理器时间资源的内核子系统。">
<meta property="og:locale" content="zh-CN">
<meta property="og:updated_time" content="2019-07-18T11:56:46.983Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Linux系统之进程调度">
<meta name="twitter:description" content="进程调度程序可看做在可运行态进程之间分配有限的处理器时间资源的内核子系统。">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Mist',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: 'Author'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://luqilinok.github.io/2019/07/17/kernel-3/">





  <title>Linux系统之进程调度 | Lu QiLin's Blog</title>
  








</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-CN">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">Lu QiLin's Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle"></p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            Home
          </a>
        </li>
      
        
        <li class="menu-item menu-item-technology">
          <a href="/categories/Technology/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            Technology
          </a>
        </li>
      
        
        <li class="menu-item menu-item-notes">
          <a href="/categories/Notes/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>
            
            Notes
          </a>
        </li>
      
        
        <li class="menu-item menu-item-personal">
          <a href="/categories/Personal/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            Personal
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br>
            
            About
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://luqilinok.github.io/2019/07/17/kernel-3/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="LuQiLin">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Lu QiLin's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">Linux系统之进程调度</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2019-07-17T14:20:30+08:00">
                2019-07-17
              </time>
            

            

            
          </span>
          
  <span class="post-updated">
    &nbsp; | &nbsp; 更新于
    <time itemprop="dateUpdated" datetime="2019-07-18T19:56:46+08:00" content="2019-07-18">
      2019-07-18
    </time>
  </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/Notes/" itemprop="url" rel="index">
                    <span itemprop="name">Notes</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>进程调度程序可看做在可运行态进程之间分配有限的处理器时间资源的内核子系统。<br><a id="more"></a></p>
<h1 id="目录"><a href="#目录" class="headerlink" title="目录"></a>目录</h1><ul>
<li><a href="#31-%E5%A4%9A%E4%BB%BB%E5%8A%A1">3.1 多任务</a></li>
<li><a href="#32-linux%E7%9A%84%E8%BF%9B%E7%A8%8B%E8%B0%83%E5%BA%A6">3.2 Linux的进程调度</a></li>
<li><a href="#33%E7%AD%96%E7%95%A5">3.3策略</a><ul>
<li><a href="#331-io%E6%B6%88%E8%80%97%E5%9E%8B%E5%92%8C%E5%A4%84%E7%90%86%E5%99%A8%E6%B6%88%E8%80%97%E5%9E%8B%E7%9A%84%E8%BF%9B%E7%A8%8B">3.3.1 I/O消耗型和处理器消耗型的进程</a></li>
<li><a href="#332-%E8%BF%9B%E7%A8%8B%E4%BC%98%E5%85%88%E7%BA%A7">3.3.2 进程优先级</a></li>
<li><a href="#333-%E6%97%B6%E9%97%B4%E7%89%87">3.3.3 时间片</a></li>
</ul>
</li>
<li><a href="#34-linux%E8%B0%83%E5%BA%A6%E7%AE%97%E6%B3%95">3.4 Linux调度算法</a><ul>
<li><a href="#341-%E8%B0%83%E5%BA%A6%E5%99%A8%E7%B1%BB">3.4.1 调度器类</a></li>
<li><a href="#342-%E5%85%AC%E5%B9%B3%E8%B0%83%E5%BA%A6">3.4.2 公平调度</a></li>
</ul>
</li>
<li><a href="#35-linux%E8%B0%83%E5%BA%A6%E7%9A%84%E5%AE%9E%E7%8E%B0">3.5 Linux调度的实现</a><ul>
<li><a href="#351-%E6%97%B6%E9%97%B4%E8%AE%B0%E8%B4%A6">3.5.1 时间记账</a></li>
<li><a href="#352-%E8%BF%9B%E7%A8%8B%E9%80%89%E6%8B%A9">3.5.2 进程选择</a></li>
<li><a href="#353-%E8%B0%83%E5%BA%A6%E5%99%A8%E5%85%A5%E5%8F%A3">3.5.3 调度器入口</a></li>
<li><a href="#354-%E7%9D%A1%E7%9C%A0%E5%92%8C%E5%94%A4%E9%86%92">3.5.4 睡眠和唤醒</a></li>
</ul>
</li>
<li><a href="#36-%E6%8A%A2%E5%8D%A0%E5%92%8C%E4%B8%8A%E4%B8%8B%E6%96%87%E5%88%87%E6%8D%A2">3.6 抢占和上下文切换</a><ul>
<li><a href="#361-%E7%94%A8%E6%88%B7%E6%8A%A2%E5%8D%A0">3.6.1 用户抢占</a></li>
<li><a href="#362-%E5%86%85%E6%A0%B8%E6%8A%A2%E5%8D%A0">3.6.2 内核抢占</a></li>
</ul>
</li>
<li><a href="#37-%E5%AE%9E%E6%97%B6%E8%B0%83%E5%BA%A6%E7%AD%96%E7%95%A5">3.7 实时调度策略</a></li>
<li><a href="#38-%E4%B8%8E%E8%B0%83%E5%BA%A6%E7%9B%B8%E5%85%B3%E7%9A%84%E7%B3%BB%E7%BB%9F%E8%B0%83%E7%94%A8">3.8 与调度相关的系统调用</a></li>
</ul>
<hr>
<h2 id="3-1-多任务"><a href="#3-1-多任务" class="headerlink" title="3.1 多任务"></a>3.1 多任务</h2><p>多任务操作系统就是能同时并发地交互执行多个进程的操作系统。多任务系统可以分为两类：</p>
<ul>
<li>非抢占式多任务：让步</li>
<li>抢占式多任务：抢占、时间片</li>
</ul>
<hr>
<h2 id="3-2-Linux的进程调度"><a href="#3-2-Linux的进程调度" class="headerlink" title="3.2 Linux的进程调度"></a>3.2 Linux的进程调度</h2><p><code>2.5</code>之前：<code>O(1)</code>调度器<br><code>2.6</code>之后：完全公平调度算法<code>CFS</code></p>
<hr>
<h2 id="3-3策略"><a href="#3-3策略" class="headerlink" title="3.3策略"></a>3.3策略</h2><h3 id="3-3-1-I-O消耗型和处理器消耗型的进程"><a href="#3-3-1-I-O消耗型和处理器消耗型的进程" class="headerlink" title="3.3.1 I/O消耗型和处理器消耗型的进程"></a>3.3.1 I/O消耗型和处理器消耗型的进程</h3><p>进程可以被分为I/O消耗型和处理器消耗型，前者是指处理器大多数时间都是再提交IO请求或者等待IO请求，而后者大多数都再运行代码，除非被抢占，这类任务通常会不停的运行，占用大量的<code>CPU</code>时间，调度器应该减少他们的执行频率。<br>调度策略通常要在两个矛盾的目标中寻找平衡：响应时间和吞吐量，Unix系统的调度程序更倾向于<code>I/O</code>消耗程序，以提供更好的程序响应时间，Linux为了保证交互式应用和桌面系统的性能，所以对进程的响应做了优化（缩短响应时间），更倾向于<code>I/O</code>消耗进程。  </p>
<hr>
<h3 id="3-3-2-进程优先级"><a href="#3-3-2-进程优先级" class="headerlink" title="3.3.2 进程优先级"></a>3.3.2 进程优先级</h3><p>Linux提供了两种优先级策略：  </p>
<ul>
<li><code>nice</code>值：范围是<code>-20</code>到<code>19</code>，默认是<code>0</code>，值越大表示优先级越低，优先级越高会获得更多的处理器时间，Linux系统中，<code>nice</code>值代表时间片的比例，而Mac OS X中，进程的<code>nice</code>值代表分配给进程的时间片的绝对值。  </li>
<li>实时优先级：其值是可配置的，默认情况下从<code>0~99</code>，越高优先级越大，任何实时进程的优先级都高于普通进程。  </li>
</ul>
<hr>
<h3 id="3-3-3-时间片"><a href="#3-3-3-时间片" class="headerlink" title="3.3.3 时间片"></a>3.3.3 时间片</h3><p>时间片是一个数值，它表明进程在抢占前能够持续运行的时间。时间片的设置有很大的问题，如果时间片太长，导致有些任务无法及时调度， 如果太短，会明显增大进程切换的开销，前面提到的<code>I/O</code>消耗型进程希望时间片越小越好，这样能够及时的处理响应，而处理器消耗型希望时间片越长越好，尽可能多的占用处理器时间，能够明显的提高高速缓存的命中率。<br>Linux的<code>CFS</code>并没有直接分配时间片到进程，而是将处理器的使用比例划分到进程，这样的话，进程获得的处理器时间和系统负载有密切的关系，这个比例还会受到<code>nice</code>值的影响。<br>Linux中的<code>CFS</code>调度器，其抢占时机取决于新的可运行程序消耗了多少处理器使用比，如果消耗的使用比比当前进程小，则新进程立刻投入运行中，抢占当前进程，否则，推迟其执行。</p>
<hr>
<h2 id="3-4-Linux调度算法"><a href="#3-4-Linux调度算法" class="headerlink" title="3.4 Linux调度算法"></a>3.4 Linux调度算法</h2><h3 id="3-4-1-调度器类"><a href="#3-4-1-调度器类" class="headerlink" title="3.4.1 调度器类"></a>3.4.1 调度器类</h3><p>Linux调度器是以模块的方式提供的，称作为调度器类，它允许多种不同的可动态添加的调度算法并存，调度属于自己的进程，每个调度器都有一个优先级，基础的调度器的代码位于<code>kernel/sched.c</code>文件中，它会按照优先级顺序遍历调度类，拥有一个可执行进程的最高优先级的调度器类生出，去选择下面要执行的一个程序。<br>完全公平调度<code>(CFS)</code>是一个针对普通进程的调度类，在Linux中被称为<code>SCHED_NORMAL</code>，<code>CFS</code>算法实现定义在文件<code>kernel/sched_fair.c</code>中。</p>
<hr>
<h3 id="3-4-2-公平调度"><a href="#3-4-2-公平调度" class="headerlink" title="3.4.2 公平调度"></a>3.4.2 公平调度</h3><p><code>CFS</code>称为公平调度器是因为它确保给每个进程公平的处理器使用比，任何进程所获得的处理器时间是由他自己和其他可运行进程<code>nice</code>值的相对差值决定的。<code>nice</code>值对时间片的作用不再是算数加权，而是几何加权。</p>
<hr>
<h2 id="3-5-Linux调度的实现"><a href="#3-5-Linux调度的实现" class="headerlink" title="3.5 Linux调度的实现"></a>3.5 Linux调度的实现</h2><p>Linux中<code>CFS</code>调度算法的代码位于文件<code>kernel/sched_fair.c</code>中，我们关注其四个组成部分：</p>
<ul>
<li>时间记账</li>
<li>进程选择</li>
<li>调度器入口</li>
<li>睡眠和唤醒</li>
</ul>
<h3 id="3-5-1-时间记账"><a href="#3-5-1-时间记账" class="headerlink" title="3.5.1 时间记账"></a>3.5.1 时间记账</h3><p><code>CFS</code>算法中记录进程运行时间的结构体如下：<br><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">sched_entity</span> &#123;</span></span><br><span class="line">	<span class="class"><span class="keyword">struct</span> <span class="title">load_weight</span>	<span class="title">load</span>;</span>		<span class="comment">/* for load-balancing */</span></span><br><span class="line">	<span class="class"><span class="keyword">struct</span> <span class="title">rb_node</span>		<span class="title">run_node</span>;</span></span><br><span class="line">	<span class="class"><span class="keyword">struct</span> <span class="title">list_head</span>	<span class="title">group_node</span>;</span></span><br><span class="line">	<span class="keyword">unsigned</span> <span class="keyword">int</span>		on_rq;</span><br><span class="line">	u64			exec_start;</span><br><span class="line">	u64			sum_exec_runtime;</span><br><span class="line">	u64			vruntime;</span><br><span class="line">	u64			prev_sum_exec_runtime;</span><br><span class="line">	u64			last_wakeup;</span><br><span class="line">	u64			avg_overlap;</span><br><span class="line">	u64			nr_migrations;</span><br><span class="line">	u64			start_runtime;</span><br><span class="line">	u64			avg_wakeup;</span><br><span class="line">	u64			avg_running;</span><br><span class="line">...</span><br></pre></td></tr></table></figure></p>
<p>这个记账信息保存在<code>task_struct</code>中的<code>ee</code>字段中，<code>update_curr()</code>函数完成了该记账功能。<br><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">static</span> <span class="keyword">void</span> <span class="title">update_curr</span><span class="params">(struct cfs_rq *cfs_rq)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="class"><span class="keyword">struct</span> <span class="title">sched_entity</span> *<span class="title">curr</span> = <span class="title">cfs_rq</span>-&gt;<span class="title">curr</span>;</span></span><br><span class="line">	u64 now = rq_of(cfs_rq)-&gt;clock_task;</span><br><span class="line">	<span class="keyword">unsigned</span> <span class="keyword">long</span> delta_exec;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">if</span> (unlikely(!curr))</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line"></span><br><span class="line">	<span class="comment">/*</span></span><br><span class="line"><span class="comment">	 * Get the amount of time the current task was running</span></span><br><span class="line"><span class="comment">	 * since the last time we changed load (this cannot</span></span><br><span class="line"><span class="comment">	 * overflow on 32 bits):</span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	delta_exec = (<span class="keyword">unsigned</span> <span class="keyword">long</span>)(now - curr-&gt;exec_start);</span><br><span class="line">	<span class="keyword">if</span> (!delta_exec)</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line"></span><br><span class="line">	__update_curr(cfs_rq, curr, delta_exec);</span><br><span class="line">	curr-&gt;exec_start = now;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">if</span> (entity_is_task(curr)) &#123;</span><br><span class="line">		<span class="class"><span class="keyword">struct</span> <span class="title">task_struct</span> *<span class="title">curtask</span> = <span class="title">task_of</span>(<span class="title">curr</span>);</span></span><br><span class="line"></span><br><span class="line">		trace_sched_stat_runtime(curtask, delta_exec, curr-&gt;vruntime);</span><br><span class="line">		cpuacct_charge(curtask, delta_exec);</span><br><span class="line">		account_group_exec_runtime(curtask, delta_exec);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>记账中最重要的变量是<code>vruntime</code>，虚拟运行时间，每隔一段时间内核会执行<code>update_curr()</code>函数，计算当前进程的执行时间，然后根据权值计算虚拟的运行时间，再加到<code>vruntime</code>变量上，Linux中进程的权值是由<code>prio_to_weight</code>这个数组定义的。<br><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="keyword">const</span> <span class="keyword">int</span> prio_to_weight[<span class="number">40</span>] = &#123;</span><br><span class="line"> <span class="comment">/* -20 */</span>     <span class="number">88761</span>,     <span class="number">71755</span>,     <span class="number">56483</span>,     <span class="number">46273</span>,     <span class="number">36291</span>,</span><br><span class="line"> <span class="comment">/* -15 */</span>     <span class="number">29154</span>,     <span class="number">23254</span>,     <span class="number">18705</span>,     <span class="number">14949</span>,     <span class="number">11916</span>,</span><br><span class="line"> <span class="comment">/* -10 */</span>      <span class="number">9548</span>,      <span class="number">7620</span>,      <span class="number">6100</span>,      <span class="number">4904</span>,      <span class="number">3906</span>,</span><br><span class="line"> <span class="comment">/*  -5 */</span>      <span class="number">3121</span>,      <span class="number">2501</span>,      <span class="number">1991</span>,      <span class="number">1586</span>,      <span class="number">1277</span>,</span><br><span class="line"> <span class="comment">/*   0 */</span>      <span class="number">1024</span>,       <span class="number">820</span>,       <span class="number">655</span>,       <span class="number">526</span>,       <span class="number">423</span>,</span><br><span class="line"> <span class="comment">/*   5 */</span>       <span class="number">335</span>,       <span class="number">272</span>,       <span class="number">215</span>,       <span class="number">172</span>,       <span class="number">137</span>,</span><br><span class="line"> <span class="comment">/*  10 */</span>       <span class="number">110</span>,        <span class="number">87</span>,        <span class="number">70</span>,        <span class="number">56</span>,        <span class="number">45</span>,</span><br><span class="line"> <span class="comment">/*  15 */</span>        <span class="number">36</span>,        <span class="number">29</span>,        <span class="number">23</span>,        <span class="number">18</span>,        <span class="number">15</span>,</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<p>权值的计算公式如下：  </p>
<blockquote>
<p> 虚拟运行时间 = 实际运行时间 * (NICE_0_LOAD / 权重）</p>
</blockquote>
<p>其中<code>NICE_0_LOAD</code>是<code>nice</code>为0的权重，可以看到权重越大，虚拟运行时间越小，而Linux会选择虚拟时间最小的进行调度。</p>
<h3 id="3-5-2-进程选择"><a href="#3-5-2-进程选择" class="headerlink" title="3.5.2 进程选择"></a>3.5.2 进程选择</h3><p><code>CFS</code>使用红黑树来组织可运行队列，并利用其迅速找到最小<code>vruntime</code>值的进程。它通过<code>__pick_next_entity()</code>函数来选择最小的<code>vruntime</code>。<br><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="class"><span class="keyword">struct</span> <span class="title">sched_entity</span> *__<span class="title">pick_last_entity</span>(<span class="title">struct</span> <span class="title">cfs_rq</span> *<span class="title">cfs_rq</span>)</span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">	<span class="class"><span class="keyword">struct</span> <span class="title">rb_node</span> *<span class="title">last</span> = <span class="title">rb_last</span>(&amp;<span class="title">cfs_rq</span>-&gt;<span class="title">tasks_timeline</span>);</span></span><br><span class="line"></span><br><span class="line">	<span class="keyword">if</span> (!last)</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">NULL</span>;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">return</span> rb_entry(last, struct sched_entity, run_node);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>当进程变为可运行状态（被唤醒）或者是通过<code>fork()</code>调用第一次创建时，<code>CFS</code>将其加入红黑树种；当进程被阻塞或者终止时，<code>CFS</code>将其从红黑树中删除。</p>
<hr>
<h3 id="3-5-3-调度器入口"><a href="#3-5-3-调度器入口" class="headerlink" title="3.5.3 调度器入口"></a>3.5.3 调度器入口</h3><p>进程调度的主要入口点是函数<code>schedule()</code>，<code>schedule()</code>会调用<code>pick_next_task()</code>从当前调度器中选择一个优先级最大的任务来调度，<code>pick_next_task()</code>会遍历调度器，从每一个调度器中执行<code>pick_next_task()</code>来选择要调度的进程，如果当前系统没有被调度的进程，则返回<code>idle</code>进程。<br><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br></pre></td><td class="code"><pre><span class="line">asmlinkage <span class="keyword">void</span> __<span class="function">sched <span class="title">schedule</span><span class="params">(<span class="keyword">void</span>)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="class"><span class="keyword">struct</span> <span class="title">task_struct</span> *<span class="title">prev</span>, *<span class="title">next</span>;</span></span><br><span class="line">	<span class="keyword">unsigned</span> <span class="keyword">long</span> *switch_count;</span><br><span class="line">	<span class="class"><span class="keyword">struct</span> <span class="title">rq</span> *<span class="title">rq</span>;</span></span><br><span class="line">	<span class="keyword">int</span> cpu;</span><br><span class="line"></span><br><span class="line">need_resched:</span><br><span class="line">	preempt_disable();</span><br><span class="line">	cpu = smp_processor_id();</span><br><span class="line">	rq = cpu_rq(cpu);</span><br><span class="line">	rcu_sched_qs(cpu);</span><br><span class="line">	prev = rq-&gt;curr;</span><br><span class="line">	switch_count = &amp;prev-&gt;nivcsw;</span><br><span class="line"></span><br><span class="line">	release_kernel_lock(prev);</span><br><span class="line">need_resched_nonpreemptible:</span><br><span class="line"></span><br><span class="line">	schedule_debug(prev);</span><br><span class="line"></span><br><span class="line">	<span class="keyword">if</span> (sched_feat(HRTICK))</span><br><span class="line">		hrtick_clear(rq);</span><br><span class="line"></span><br><span class="line">	spin_lock_irq(&amp;rq-&gt;lock);</span><br><span class="line">	update_rq_clock(rq);</span><br><span class="line">	clear_tsk_need_resched(prev);</span><br><span class="line"></span><br><span class="line">	<span class="keyword">if</span> (prev-&gt;state &amp;&amp; !(preempt_count() &amp; PREEMPT_ACTIVE)) &#123;</span><br><span class="line">		<span class="keyword">if</span> (unlikely(signal_pending_state(prev-&gt;state, prev)))</span><br><span class="line">			prev-&gt;state = TASK_RUNNING;</span><br><span class="line">		<span class="keyword">else</span></span><br><span class="line">			deactivate_task(rq, prev, <span class="number">1</span>);</span><br><span class="line">		switch_count = &amp;prev-&gt;nvcsw;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	pre_schedule(rq, prev);</span><br><span class="line"></span><br><span class="line">	<span class="keyword">if</span> (unlikely(!rq-&gt;nr_running))</span><br><span class="line">		idle_balance(cpu, rq);</span><br><span class="line"></span><br><span class="line">	put_prev_task(rq, prev);</span><br><span class="line">	next = pick_next_task(rq);</span><br><span class="line"></span><br><span class="line">	<span class="keyword">if</span> (likely(prev != next)) &#123;</span><br><span class="line">		sched_info_switch(prev, next);</span><br><span class="line">		perf_event_task_sched_out(prev, next, cpu);</span><br><span class="line"></span><br><span class="line">		rq-&gt;nr_switches++;</span><br><span class="line">		rq-&gt;curr = next;</span><br><span class="line">		++*switch_count;</span><br><span class="line"></span><br><span class="line">		context_switch(rq, prev, next); <span class="comment">/* unlocks the rq */</span></span><br><span class="line">		<span class="comment">/*</span></span><br><span class="line"><span class="comment">		 * the context switch might have flipped the stack from under</span></span><br><span class="line"><span class="comment">		 * us, hence refresh the local variables.</span></span><br><span class="line"><span class="comment">		 */</span></span><br><span class="line">		cpu = smp_processor_id();</span><br><span class="line">		rq = cpu_rq(cpu);</span><br><span class="line">	&#125; <span class="keyword">else</span></span><br><span class="line">		spin_unlock_irq(&amp;rq-&gt;lock);</span><br><span class="line"></span><br><span class="line">	post_schedule(rq);</span><br><span class="line"></span><br><span class="line">	<span class="keyword">if</span> (unlikely(reacquire_kernel_lock(current) &lt; <span class="number">0</span>))</span><br><span class="line">		<span class="keyword">goto</span> need_resched_nonpreemptible;</span><br><span class="line"></span><br><span class="line">	preempt_enable_no_resched();</span><br><span class="line">	<span class="keyword">if</span> (need_resched())</span><br><span class="line">		<span class="keyword">goto</span> need_resched;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p><code>pick_next_task</code>实现：<br><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"> * 挑选醉倒优先级的任务</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">static</span> <span class="keyword">inline</span> <span class="class"><span class="keyword">struct</span> <span class="title">task_struct</span> *</span></span><br><span class="line"><span class="class"><span class="title">pick_next_task</span>(<span class="title">struct</span> <span class="title">rq</span> *<span class="title">rq</span>)</span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">	<span class="keyword">const</span> <span class="class"><span class="keyword">struct</span> <span class="title">sched_class</span> *<span class="title">class</span>;</span></span><br><span class="line">	<span class="class"><span class="keyword">struct</span> <span class="title">task_struct</span> *<span class="title">p</span>;</span></span><br><span class="line"></span><br><span class="line">	<span class="comment">/*</span></span><br><span class="line"><span class="comment">	 * 优化：我们知道所有任务都在公平类中，就可以直接调用公平类中的函数选择下一个进程</span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">if</span> (likely(rq-&gt;nr_running == rq-&gt;cfs.nr_running)) &#123;</span><br><span class="line">		p = fair_sched_class.pick_next_task(rq);</span><br><span class="line">		<span class="keyword">if</span> (likely(p))</span><br><span class="line">			<span class="keyword">return</span> p;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="class"><span class="keyword">class</span> = <span class="title">sched_class_highest</span>;</span></span><br><span class="line">	<span class="keyword">for</span> ( ; ; ) &#123;</span><br><span class="line">		p = class-&gt;pick_next_task(rq);</span><br><span class="line">		<span class="keyword">if</span> (p)</span><br><span class="line">			<span class="keyword">return</span> p;</span><br><span class="line">		<span class="comment">/*</span></span><br><span class="line"><span class="comment">		 * Will never be NULL as the idle class always</span></span><br><span class="line"><span class="comment">		 * returns a non-NULL p:</span></span><br><span class="line"><span class="comment">		 */</span></span><br><span class="line">		<span class="class"><span class="keyword">class</span> = <span class="title">class</span>-&gt;<span class="title">next</span>;</span></span><br><span class="line">	&#125;</span><br></pre></td></tr></table></figure></p>
<hr>
<h3 id="3-5-4-睡眠和唤醒"><a href="#3-5-4-睡眠和唤醒" class="headerlink" title="3.5.4 睡眠和唤醒"></a>3.5.4 睡眠和唤醒</h3><p>睡眠的过程：进程把自己置为休眠状态，从可执行红黑树种移出，放入等待队列，然后调用<code>schedule()</code>选择和执行下一个进程。唤醒的过程刚好相反。休眠的两种相关的进程状态：<code>TASK_INTERRUPTIBLE</code>和<code>TASK_UNINTERRUPTIBLE</code>，他们的唯一区别是处于<code>TASK_UNINTERRUPTIBLE</code>的进程会忽略信号，而处于<code>TASK_INTERRUPTIBLE</code>状态的进程如果接受到一个信息，会被提前唤醒并响应该信号。</p>
<hr>
<h2 id="3-6-抢占和上下文切换"><a href="#3-6-抢占和上下文切换" class="headerlink" title="3.6 抢占和上下文切换"></a>3.6 抢占和上下文切换</h2><p>上下文切换就是从一个进程切换到下一个要执行的进程，由定义在<code>kernel/sched.c</code>中的<code>context_switch()</code>函数负责处理，当一个新的进程被选出来准备投入运行的时候，<code>schedule()</code>就会调用该函数。它完成两项基本的工作：</p>
<ul>
<li>调用<code>&lt;asm/mmu_context.h&gt;</code>中的<code>switch_mm()</code>，该函数负责把虚拟内存从上一个进程切换到下一个进程。</li>
<li>调用<code>&lt;asm/system.h&gt;</code>中的<code>switch_to()</code>该函数负责从上一个进程的处理器状态切换到新的进程的处理器状态，这包括保存、恢复栈信息和寄存器信息，还有其他任何与体系结构相关的状态信息，都必须以每个进程为对象进行管理和保存。</li>
</ul>
<p><code>schedule()</code>函数的执行时机是通过<code>need_resched</code>这个标志来判断的。</p>
<h3 id="3-6-1-用户抢占"><a href="#3-6-1-用户抢占" class="headerlink" title="3.6.1 用户抢占"></a>3.6.1 用户抢占</h3><p>内核即将返回用户空间的时候，如果<code>need_reched</code>标志被设置，会导致<code>schedule()</code>被调用。用户抢占在以下情况下产生：</p>
<ul>
<li>从系统调用返回用户空间时</li>
<li>从中断处理程序返回用户空间时</li>
</ul>
<hr>
<h3 id="3-6-2-内核抢占"><a href="#3-6-2-内核抢占" class="headerlink" title="3.6.2 内核抢占"></a>3.6.2 内核抢占</h3><p>内核抢占需要查看<code>thread_info</code>中的<code>preempt_count</code>计数器，这个计数器记录当前进程使用锁的个数，只有当前进程没有锁的时候，进程才能被抢占。</p>
<hr>
<h2 id="3-7-实时调度策略"><a href="#3-7-实时调度策略" class="headerlink" title="3.7 实时调度策略"></a>3.7 实时调度策略</h2><p>Linux中有两种实时调度策略：<code>SCHED_FIFO</code>和<code>SCHED_RR</code>，具体的实现在<code>kernel/sched_rt.c</code>。<br><code>SCHED_FIFO</code>：先入先出的调度策略，只有等当前进程自己受阻塞或者显式地释放处理器为止，才能调度后面的进程执行。<br><code>SCHED_RR</code>：轮询式调度策略，带有时间片，时间片用完，在同一优先级的其他实时进程被轮流调度。<br>实时进程的优先级比普通进程要高。</p>
<hr>
<h2 id="3-8-与调度相关的系统调用"><a href="#3-8-与调度相关的系统调用" class="headerlink" title="3.8 与调度相关的系统调用"></a>3.8 与调度相关的系统调用</h2><table>
<thead>
<tr>
<th>系统调用</th>
<th>描述</th>
</tr>
</thead>
<tbody>
<tr>
<td>nice()</td>
<td>设置进程的nice值</td>
</tr>
<tr>
<td>sched_setscheduler()</td>
<td>设置进程的调度策略</td>
</tr>
<tr>
<td>sched_getscheduler()</td>
<td>获取进程的调度策略</td>
</tr>
<tr>
<td>sched_setparam()</td>
<td>设置进程的实时优先级</td>
</tr>
<tr>
<td>sched_getparam()</td>
<td>获取进程的实时优先级</td>
</tr>
<tr>
<td>sched_get_priority_max()</td>
<td>获取实时优先级的最大值</td>
</tr>
<tr>
<td>sched_get_priority_min()</td>
<td>获取实时优先级的最小值</td>
</tr>
<tr>
<td>sehed_rr_get_interval()</td>
<td>获取进程的时间片值</td>
</tr>
<tr>
<td>sched_setaffinity()</td>
<td>设置进程的处理器的亲和力</td>
</tr>
<tr>
<td>sched_getaffinity()</td>
<td>获取进程的处理器的亲和力</td>
</tr>
<tr>
<td>sched_yield()</td>
<td>暂时让出处理器</td>
</tr>
</tbody>
</table>

      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2019/07/17/kernel-2/" rel="next" title="Linux系统之进程管理">
                <i class="fa fa-chevron-left"></i> Linux系统之进程管理
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2019/07/17/kernel-4/" rel="prev" title="Linux系统之系统调用">
                Linux系统之系统调用 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            Table of Contents
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            Overview
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <p class="site-author-name" itemprop="name">LuQiLin</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives">
              
                  <span class="site-state-item-count">80</span>
                  <span class="site-state-item-name">posts</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                
                  <span class="site-state-item-count">1</span>
                  <span class="site-state-item-name">categories</span>
                
              </div>
            

            

          </nav>

          

          

          
          

          
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#目录"><span class="nav-number">1.</span> <span class="nav-text">目录</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#3-1-多任务"><span class="nav-number">1.1.</span> <span class="nav-text">3.1 多任务</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#3-2-Linux的进程调度"><span class="nav-number">1.2.</span> <span class="nav-text">3.2 Linux的进程调度</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#3-3策略"><span class="nav-number">1.3.</span> <span class="nav-text">3.3策略</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#3-3-1-I-O消耗型和处理器消耗型的进程"><span class="nav-number">1.3.1.</span> <span class="nav-text">3.3.1 I/O消耗型和处理器消耗型的进程</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#3-3-2-进程优先级"><span class="nav-number">1.3.2.</span> <span class="nav-text">3.3.2 进程优先级</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#3-3-3-时间片"><span class="nav-number">1.3.3.</span> <span class="nav-text">3.3.3 时间片</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#3-4-Linux调度算法"><span class="nav-number">1.4.</span> <span class="nav-text">3.4 Linux调度算法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#3-4-1-调度器类"><span class="nav-number">1.4.1.</span> <span class="nav-text">3.4.1 调度器类</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#3-4-2-公平调度"><span class="nav-number">1.4.2.</span> <span class="nav-text">3.4.2 公平调度</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#3-5-Linux调度的实现"><span class="nav-number">1.5.</span> <span class="nav-text">3.5 Linux调度的实现</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#3-5-1-时间记账"><span class="nav-number">1.5.1.</span> <span class="nav-text">3.5.1 时间记账</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#3-5-2-进程选择"><span class="nav-number">1.5.2.</span> <span class="nav-text">3.5.2 进程选择</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#3-5-3-调度器入口"><span class="nav-number">1.5.3.</span> <span class="nav-text">3.5.3 调度器入口</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#3-5-4-睡眠和唤醒"><span class="nav-number">1.5.4.</span> <span class="nav-text">3.5.4 睡眠和唤醒</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#3-6-抢占和上下文切换"><span class="nav-number">1.6.</span> <span class="nav-text">3.6 抢占和上下文切换</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#3-6-1-用户抢占"><span class="nav-number">1.6.1.</span> <span class="nav-text">3.6.1 用户抢占</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#3-6-2-内核抢占"><span class="nav-number">1.6.2.</span> <span class="nav-text">3.6.2 内核抢占</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#3-7-实时调度策略"><span class="nav-number">1.7.</span> <span class="nav-text">3.7 实时调度策略</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#3-8-与调度相关的系统调用"><span class="nav-number">1.8.</span> <span class="nav-text">3.8 与调度相关的系统调用</span></a></li></ol></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2019</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">LuQiLin</span>

  
</div>


  <div class="powered-by">Powered by <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a></div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">Theme &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Mist</a> v5.1.4</div>




        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  

  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  





  

  

  

  
  

  

  

  

</body>
</html>
